Key recovery attack on BIP32-Ed25519
Non-hardenedにおける困難性
支払人が受取人のために新しい公開鍵を導出する。この公開鍵は受取人だけが秘密鍵に導出できる。
支払人が公開鍵といくつかの追加インプットをハッシュ化し新しい秘密鍵を生成する。
対応する公開鍵をderiveする。
この公開鍵を受取人の公開鍵に加算する。
受取人はこの秘密鍵と自身の元の秘密鍵を使って、新しい公開鍵に対応する秘密鍵を加算により導出することができる。
つまり、拡張公開鍵を公開前提
例えば、ed25519のorderは8*IでIは252bit prime。
なので秘密鍵としては、low three bitsがzeroedな255bit integer scalarsを選ぶ。
Key derivation works on an Edwards curve
Next-Generation Hidden Services in Tor
Torにおけるアルゴリズム
Security proof in ROM
priavate key演算を加算ではなく乗算に。
By Chain
conceivably enables small subgroup attacks
https://gyazo.com/7ffab03221574d435482b30e3b3ea10c
Z_K + k_Lが2^255をoverflowし、module nされる可能性がある。
これにより、k_Lのhighest bitsがclear or setの保証がなくなりeddsa keysの定義と矛盾する。
timing attackの対象に。
By Evernym
Chainのtiming attackを排除したが、key recovery attackを防ぐために開発者がHKDのdepth checkをする必要性。
Cardano採用アルゴリズム
https://gyazo.com/8b7424e46fefbe68485ba878184b6990
k_Lのlast byteのthird highest bitがzeroじゃなかったらkを作り直し。
このバリデーションを通過した後にed25519 specに合うように他のbitsをセット
Z_Lを32bytes -> 28bytesのtrimすることでchainでの問題に対処
Security
Maser key security
512-bits extended keyで6bits set
ed25519は128bits security
extended keyに対する2^506 brute-force or master secretに対する2^256
child key collisions
ed25519 spec
last byteのhighest bitはclear
last byteのsecond highest bitはset
highest active bitを探索する乗算アルゴリズムでのtiming leakageを防ぐ
first byteのthree lowest bitsはclear (low-level attacks)
BIP32-Ed25519 attacksのassumptions
署名前にすぐにclampingするEd25519ライブラリを利用
key derivationで多数の階層に潜り多数の少額決済をする能力をもつ攻撃者
BIP32-Ed2559では制限を設けているがシンプルな制限では全てのkeyを保護できず、開発者によってはdeptch checkをしない場合もある
Cofactorsベースの攻撃
ed25519の場合はcofactor 8なのでprivate keyは255 bit integer scalarsのlow three bitsはzeroed。
なので、key derivationにおけるsclar additionはmod 8 * l (l=252 bit prime)で行われなければならない。
255 bit scalarを252 bit scalarにbit shftしてから、mod l で加算を行い、low three bitsをzeroedして255 bit scalarにshifting backすることで、mod lの加算らmod 8 * lの加算を実装することが可能。
BIP32-Ed25519ではscalarを224 bitsに制限することでmod 2^256。
Constant-timeベースの攻撃
Additive vs multiplicative
Consider hardened BIP-32 derivation paths
HMAC-based Hierarchical Key Derivation
there are a number of problems with attempting to specify a scheme like this on an elliptic curve with cofactors (such as the cofactor 8 curve Curve25519/"edwards25519"), and specifically the "clamping" operations:
Interest in an "Ed25519-HD" standard?
Feature request: Ristretto (i.e. safe elliptic curve group APIs)
Almost all hierachical key derivation schemes for ed25519 have vulnerabilities due to the "bit clamping" used in ed25519.
Account signatures and keys in Polkadot
Hierarchical derivations on Ed25519
Key recovery attack on BIP32-Ed25519
BIP32-Ed25519 Hierarchical Deterministic Keys over a Non-linear Keyspace
SLIP-0010 : Universal private key derivation from master private key
For ed25519 only hardened key generation from Private parent key to private child key is supported.
BLS Signature Scheme Specificiation
the best possible concrete security is that of 251-bit hash rather than a 256-bit hash.
なので、decryption keyへのハッシュ値をとるとき最後の5bitを消す
https://gyazo.com/39081dcb594c38d2beede9a10723ecde
Note that most Ed25519 implementations mask the lower 3 bits ("clamping"). So 1 will produce the same public key as 2 or 3. This is a simple way to prevent small-subgroup attacks. But once again, most applications usually just generate 256 random bits, and don't really have to care about this.
refs